#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/4sum/description

直接在lintcode q89基础上修改
"""

class Solution:
    """
    @param A: An integer array
    @param k: A positive integer (k <= length(A))
    @param target: An integer
    @return: An integer
    """
    def fourSum(self, nums, target):
        self.nums = sorted(nums)
        self.len = len(self.nums)
        self.target = target
        self.results_memory = {}
        self.k = 4

        return self.match_from_min(target, self.k, 0)[1]

    def match_from_min(self, target, k, from_min_idx):
        # 最小值从from_min_idx开始匹配, 匹配target, 还剩下k个数可用
        key = (target, k, from_min_idx)
        b_and_paths = self.results_memory.get(key)
        if b_and_paths is not None:
            return b_and_paths

        # print('key', key)

        if target == 0 and k == 0:
            # cnt = 1
            return True, []

        if k <= 0:
            # return False, None
            return False, []

        else:
            paths = []
            for min_idx in range(from_min_idx, self.len-k+1):
                # print('k', k, from_min_idx, min_idx)

                # 通过这种方式, 禁止相同的解决方案
                if min_idx > from_min_idx:
                    if self.nums[min_idx] == self.nums[min_idx-1]:
                        continue

                cur_ele = self.nums[min_idx]
                remain = target - cur_ele

                if remain < self.nums[from_min_idx] and k-1 > 0:
                    # 用来剪枝
                    # print('hit')
                    break

                # 注意这里min_idx + 1, 表示不使用重复数字
                has, sub_paths = self.match_from_min(remain, k-1, min_idx+1)
                if has:
                    if not sub_paths:
                        paths.append( [cur_ele] )
                    else:
                        for sub_path in sub_paths:
                            paths.append( [cur_ele] + sub_path)
                            # print(paths)

        b = bool(paths)
        self.results_memory[key] = b, paths
        # print(key, paths)
        return b, paths


def test():
    s = Solution()

    lst = [1, 2, 3, 5]
    print( s.fourSum(lst, 10) )

    lst = [1, 2, 3, 4]
    print( s.fourSum(lst, 10) )

    lst = [1,0,-1,0,-2,2]
    print( s.fourSum(lst, 0) )

    lst = [1,0,-1,0,-2,2]
    print( s.fourSum(lst, -2) )

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
